1556F - Sports Betting - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
typedef std::string str;
#define sei set<int>
#define sell set<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vvll vector<vll>
#define vld vector<ld>
#define vstr vector<str>
#define vpii vector<pii>
#define vpll vector<pll>
#define bit(n,i) ((n>>i)&1)
#define bits(i) __builtin_popcountll(i)
#define all(v) v.begin(),v.end()
#define uniq(v) sort(all(v)),v.resize(unique(all(v))-v.begin())
#define foa(i,v) for(auto i : v)
#define fo(i,a,b) for(int i=a;i<b;i++)
#define fo_(i,a,b) for(int i=a;i>b;i--)
#define M(a) memset(a,0,sizeof a)
#define M_(a) memset(a ,-1,sizeof a)
#define deb(x)  cerr << #x << " = " << x << endl
#define pb push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define OK order_of_key
#define FO find_by_order
#define nmax 1000100
const ld PI = 3.141592653589793238462643383279;
const ll inf = std::numeric_limits<ll>::max();
const int infint = std::numeric_limits<int>::max();
const ll mod = 1e9+7;
using namespace __gnu_pbds;
using namespace std;
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
ll inv(ll a, ll m = mod)
{
    ll m0 = m;
    ll y = 0, x = 1;
    ll a0 = a;
 
    if (m == 1)
      return 0;
 
    while (a > 1)
    {
        ll q = a / m;
        ll t = m;
        m = a % m, a = t;
        t = y;
        y = x - q * y;
        x = t;
    }
 
    if (x < 0)
       x += m0;
 
    y = (1-x*(a0))/m0;  // baraye x*a0+y*m0 = 1 hast!
 
    return x;
}
 
ll fact[nmax];
ll invfact[nmax];
 
ll c(ll n, ll r){
    if(r < 0 || n < 0) return 0;
    if(n < r) return 0;
    return fact[n]*invfact[n-r]%mod*invfact[r]%mod;
}
void init_c(){ //in ro hatman to main bezar!!! nmax ham taghir bede
    fact[0] = 1;
    fo(i,1,nmax) fact[i] = i*fact[i-1]%mod;
    invfact[nmax-1] = inv(fact[nmax-1]);
    fo_(i,nmax-2,-1) invfact[i] = invfact[i+1]*(i+1)%mod;
}
 
ll a[15];
ll invv[15][15];
ll ans[nmax];
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    fo(i,0,n) cin >> a[i];
    if(n == 1) return cout << 1,0;
    init_c();
    fo(i,0,n) fo(j,0,n) invv[i][j] = inv(a[i]+a[j]);
 
    fo(mask,1,1<<n){
        ans[mask] = 1;
        fo(i,0,n) fo(j,0,n){
            if(bit(mask,i) && !bit(mask,j)) ans[mask] = ans[mask]*invv[i][j]%mod*a[i]%mod;
        }
    }
 
    fo(mask,1,1<<n){
        // check all submasks of a mask 'allmask'
        int s = mask;
        while (s > 0) {
            ll kos = 1;
            fo(i,0,n) fo(j,0,n) if(bit(mask,i) && !bit(s,i) && !bit(mask,j)) kos = kos*invv[i][j]%mod*a[i]%mod;
            if(mask != s) ans[mask] = (ans[mask]-kos*ans[s]%mod+mod)%mod;
            s = (s-1) & mask;
        }
        // halat sefr ro bayad inja barresi koni
    }
 
    ll out = 0;
    fo(mask,1,1<<n){
        out += bits(mask)*ans[mask]%mod;
    }
    //cout << ans[3] << ' ' << ans[6] << endl;
    out %= mod;
    cout << out;
 
    return 0;
}